#!/usr/bin/python
from __future__ import division
import sys
#collaborators: Nathan Weatherly, Max Daum. 

#Running instructions: ./SI7JoePuccio.py [Broken_file.txt] [AB_file.txt] [number of runs]


#introduce new structures to appease Jack 
class Point: 
	x = 0
	y = 0

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def lessThan(self, otherPoint):
		if self.x<otherPoint.x:
			return True
		elif self.x>otherPoint.x:
			return False
		elif self.y<otherPoint.y:
			return True 
		else:
			return False

class Vector: 
	xCompon = 0
	yCompon = 0 

	#vector from A to B
	def __init__(self, pointA, pointB):
		self.xCompon = pointB.x - pointA.x 
		self.yCompon = pointB.y - pointA.y 


class Flag: 
	x = 0
	y = 0
	slope = 0
	color = "Blank"
	flagType = "none"
	owner = None

	def __init__(self, x, y, slope, color, flagType, owner):
		self.x = x
		self.y = y
		self.slope = slope
		self.color = color 
		self.flagType = flagType
		self.owner = owner

def switchFlags(flagA, flagB): 
	#1 means switch, -1 means don't
	if flagA.x < flagB.x:
		return -1
	elif flagA.x > flagB.x:
		return 1 
	elif flagA.y < flagB.y:
		return -1 
	elif flagA.y > flagB.y: 
		return 1 
	elif flagA.flagType == "Terminal" and flagB.flagType == "Start":
		return -1 
	elif flagA.flagType == "Start" and flagB.flagType == "Terminal":
		return 1 
	elif flagA.slope > flagB.slope: 
		return -1
	elif flagA.slope < flagB.slope: 
		return 1
	elif flagA.color == "Blue" and flagB.color == "Red":
		return -1 
	elif flagA.color == "Red" and flagB.color == "Blue":
		return 1
	else: 
		return 0
		#return "dude, stop messin' around. Overlapping lines of same color."

#STILL NEED TO ADD COMPARISON FOR IF POINT LEFT, RIGHT, OR ON LINE. Don't know why. 
class Segment:
	firstPoint = Point(0, 0)
	secondPoint = Point(0, 0)
	color = "Blank"
	startFlag = Flag(0,0,0,"Blank","None",None)
	terminalFlag = Flag(0,0,0,"Blank","None",None)
	flagsSwapped = False
	segmentNumber = 0 

	def __init__(self, pointA, pointB, inputColor, segmentNumber):
		self.firstPoint = pointA
		self.secondPoint = pointB
		self.color = inputColor
		self.segmentNumber = segmentNumber
		self.createFlags(self.firstPoint,self.secondPoint,self.color)

	def createFlags(self,firstPoint,secondPoint,inputColor):
		#calculate slope
		if (firstPoint.x - secondPoint.x) == 0:
			slope = float("inf")
		else: 
			slope = (firstPoint.y - secondPoint.y) / (firstPoint.x - secondPoint.x)
		if(firstPoint.lessThan(secondPoint)): #then firstPoint is startFlag
			self.startFlag = Flag(firstPoint.x,firstPoint.y, slope, self.color, "Start" ,self) 
			self.terminalFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Terminal" , self)
		else:
			self.terminalFlag = Flag(firstPoint.x,firstPoint.y,slope,self.color, "Terminal" ,self) 
			self.startFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Start", self)
			flagsSwapped = True

	def relationToPoint(self,point):
		#use cross product to determine relation
		crazyCrossProd = ((self.secondPoint.x - self.firstPoint.x) * (point.y - self.firstPoint.y) - (self.secondPoint.y - self.firstPoint.y) * (point.x - self.firstPoint.x))
		if crazyCrossProd>0:
			return "Left"
		elif crazyCrossProd<0:
			return "Right"
		else:
			if self.firstPoint.y == float("inf"):
				return "Right"
			elif self.firstPoint.y == float("-inf"):
				return "Left"
			return "On Line"

	def __str__(self):
		return "({0},{1}),({2},{3})".format(self.firstPoint.x, self.firstPoint.y, self.secondPoint.x, self.secondPoint.y)


def outerProduct(vectorA, vectorB):
	return (vectorA.xCompon * vectorB.yCompon) - (vectorA.yCompon * vectorB.xCompon)

def determineIfIntersects(segmentA, segmentB):
	#see CLRS 33 for more info. 
	P_R = Vector(segmentA.firstPoint, segmentB.firstPoint)
	P_S = Vector(segmentA.firstPoint, segmentB.secondPoint)
	P_Q = Vector(segmentA.firstPoint, segmentA.secondPoint)
	Q_R = Vector(segmentA.secondPoint, segmentB.firstPoint)
	S_R = Vector(segmentB.secondPoint, segmentB.firstPoint)

	PR_times_PQ = outerProduct(P_R,P_Q)
	PS_times_PQ = outerProduct(P_S,P_Q)
	PR_times_SR = outerProduct(P_R,S_R)
	QR_times_SR = outerProduct(Q_R,S_R)

	return (PR_times_PQ * PS_times_PQ <0 and PR_times_SR * QR_times_SR <0)

def orderOfSegments(segmentA, segmentB): 
	if segmentB.relationToPoint(segmentA.firstPoint) == "Left":
		return 1
	elif segmentB.relationToPoint(segmentA.firstPoint) == "Right":
		return -1
	else:
		return 0

def printIntersect(segmentA, segmentB):
	print "{0}{1} intersects {2}{3}".format("B" if segmentA.color=="Blue" else "R",segmentA.segmentNumber, "B" if segmentB.color=="Blue" else "R",segmentB.segmentNumber)

def findXsection(flag, currestSegmentsThatCouldMatter):
	for seg in currestSegmentsThatCouldMatter:
		if determineIfIntersects(flag.owner, seg):
			printIntersect(flag.owner,seg)

class listDataStructure:

	segments = []

	def __init__(self,numberOfSegmentsOfAColor):
		#create top and bottom sentinel 
		topSentinel = Segment(Point(float("-inf"),float("inf")),Point(float("inf"),float("inf")),"Blank",numberOfSegmentsOfAColor+1)
		bottomSentinel = Segment(Point(float("-inf"),float("-inf")),Point(float("inf"),float("-inf")),"Blank",0)
		self.segments.append(topSentinel)
		self.segments.append(bottomSentinel)

	def insert(self,passedSegment):
		self.segments.append(passedSegment)

	def remove(self,passedSegment):
		self.segments.remove(passedSegment)

def printSegments(arrayOfSegments):
	for segment in arrayOfSegments:
		print "{0} {1}".format(segment.segmentNumber,segment)
	print "-----"


numberOfRuns = sys.argv[3]
SI6Output = sys.argv[2] 


with open(sys.argv[1], 'r') as testFile:
 
  firstLine = testFile.readline()
  numberOfRed = int(firstLine.split()[0])
  numberOfBlue = int(firstLine.split()[1])
  numberOfProposedCrosses = int(firstLine.split()[2])

  blueLines = []
  redLines = []

  for incrementer in range(0,numberOfRed):
  	nextLine = testFile.readline()
  	redLines.append([nextLine.split()[0],nextLine.split()[1],nextLine.split()[2],nextLine.split()[3]])

  for incrementer in range(0,numberOfBlue):
  	nextLine = testFile.readline()
  	blueLines.append([nextLine.split()[0],nextLine.split()[1],nextLine.split()[2],nextLine.split()[3]])

segmentNumber = 1
currentRedSegments = []
currentBlueSegments = []
allSegments = [] 


for redLine in redLines:

	redA = Point(int(redLine[0]),int(redLine[1]))
	redB = Point(int(redLine[2]),int(redLine[3]))
	redSegment = Segment(redA, redB, "Red", segmentNumber)
	allSegments.append(redSegment)
	segmentNumber = segmentNumber + 1

segmentNumber = 1

for blueLine in blueLines:

	blueA = Point(int(blueLine[0]),int(blueLine[1]))
	blueB = Point(int(blueLine[2]),int(blueLine[3]))
	blueSegment = Segment(blueA, blueB, "Blue", segmentNumber)
	allSegments.append(blueSegment)
	segmentNumber = segmentNumber + 1


sortedFlags = sorted([segment.startFlag for segment in allSegments] + [segment.terminalFlag for segment in allSegments], cmp=switchFlags)


#for flag in sortedFlags:
#	print "{0} {1} {2}".format(flag.owner.segmentNumber,flag.color,flag.flagType)

listDataStructure = listDataStructure(len(blueLines))


'''
for i in range(0,int(numberOfRuns)):
	for flag in sortedFlags:
		if flag.flagType=="Start":
			brolistDataStructure.insert(flag.owner)
			#call sweep here
			if i == int(numberOfRuns)-1:
				print "{0}{1}{2} {3}".format(flag.owner.segmentNumber,"R" if flag.color=="Red" else "B","S" if flag.flagType=="Start" else "T",examineFlag(flag,listDataStructure.segments))
				#printSegments(listDataStructure.segments)
			
		else: 
			if i == int(numberOfRuns)-1:
				print "{0}{1}{2} {3}".format(flag.owner.segmentNumber,"R" if flag.color=="Red" else "B","S" if flag.flagType=="Start" else "T",examineFlag(flag,listDataStructure.segments))
			brolistDataStructure.remove(flag.owner)
			#call sweep here

''' 
for i in range(0, int(numberOfRuns)):

	'''
		newDataStruct = listDataStructure(len(blueLines))

		for flag in sortedFlags:
			if flag.flagType=="Start":
				if i == int(numberOfRuns)-1:
					newDataStruct.insert(flag.owner)
	'''
	for flag in sortedFlags: 
		if flag.flagType=="Start":
			if flag.color=="Blue":
				currentBlueSegments.append(flag.owner)
				'''
			for flag in sortedFlags:
		if i == int(numberOfRuns)-1:
					print "{0}{1}{2} {3}".format(flag.owner.segmentNumber,"R" if flag.color=="Red" else "B","S" if flag.flagType=="Start" else "T",examineFlag(flag,newDataStruct.segments))
				'''
				findXsection(flag, currentRedSegments)
			else:
				currentRedSegments.append(flag.owner)
				'''
		 do within sortedFlags:
				if i == int(numberOfRuns)-1:
					format(flag.owner.segmentNumber,"R" if flag.color=="Red" else "B","S" if flag.flagType=="Start" else "T",examineFlag(flag,newDataStruct.segments))
				'''
				findXsection(flag, currentBlueSegments)
		else:
			currentBlueSegments.remove(flag.owner) if flag.color=="Blue" else currentRedSegments.remove(flag.owner)
			'''
			brolistDataStructure.remove(flag.owner)
			#call sweep here
			'''